package codetop.microsoft.T354;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-09-08 12:31:20 星期四
 */
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0])
                return a[0] - b[0];
            return b[1] - a[1];
        });
        int k = 0;
        int[] low = new int[envelopes.length];
        low[0] = envelopes[0][1];
        for (int i=1; i<envelopes.length; ++i) {
            if (envelopes[i][1] > low[k])
                low[++k] = envelopes[i][1];
            else {
                int idx = lowerBound(low, k+1, envelopes[i][1]);
                low[idx] = envelopes[i][1];
            }
        }
        return k + 1;
    }

    private int lowerBound(int[] arr, int len, int target) {
        int left = 0, right = len;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
}